from math_utils import argmin
from two_d_utils import vector, cosine, cross_product
from quicksort import quicksort


def graham_scan(points):
    base_idx = argmin(points, key=lambda x: x[1])
    points[base_idx], points[-1] = points[-1], points[base_idx]
    base = points[-1]
    points.pop()
    quicksort(points, key=lambda x: -cosine(vector(base, x), (1, 0)))
    # points.sort(key=lambda x: cosine(vector(base, x), (1, 0)), reverse=True)

    stack = [base, points[0]]
    for i in range(1, len(points)):
        next_point = points[i]

        # 如果向外转弯，则出栈栈顶点
        while cross_product(vector(stack[-2], stack[-1]), vector(stack[-1], next_point)) < 0:
            stack.pop()
        # 新顶点入栈
        stack.append(next_point)
    return stack
